package com.sicheng.lc.周赛.分类.公共缀orKmp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/25 12:31
 */
public class 构造字符串的总得分和 {
    //https://leetcode.cn/problems/sum-of-scores-of-built-strings/
    public long sumScores(String s) {
        long res = s.length();
        int[] z = new int[s.length()];
        for (int i = 1, l = 0, r = 0; i < s.length(); i++) {
            if (i <= r && z[i - l] <= r - i + 1) {
                z[i] = z[i - l];
            } else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < s.length() && s.charAt(z[i]) == s.charAt(i + z[i]))
                    z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
            res += z[i];
        }

        return res;
    }
}
